package leetCode;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 301. 删除无效的括号
 * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 * <p>
 * 返回所有可能的结果。答案可以按 任意顺序 返回。
 *
 * @author 司松坡
 * @createTime 2025年01月07日
 */
public class LeetCode301 {

    List<String> list = new ArrayList<>();
    int length;

    public List<String> removeInvalidParentheses(String s) {
        int i = 0;
        int j = 0;
        int q = 0;
        int l = s.length();
        for (int k = 0; k < l; k++) {
            if (s.charAt(k) == '(') {
                i++;
            } else if (s.charAt(k) == ')') {
                if (j < i) {
                    j++;
                }
            } else {
                q++;
            }
        }
        length = 2 * j + q;
        solve(s, 0, "", 0, 0);
        if (list.size() == 0){
            list.add("");
        }
        return list;
    }

    private void solve(String s, int i, String l, int a, int b) {
        if (i == s.length()) {
            return;
        }
        if (s.charAt(i) == '(') {
            l = l + '(';
            a++;
        } else if (s.charAt(i) == ')') {
            if (a > b) {
                l = l + ')';
                b++;
            }
        } else {
            l = l + s.charAt(i);
        }
        if (l.length() == length && !list.contains(l) && a == b) {
            list.add(l);
        }
        solve(s, i + 1, l, a, b);
        if (l.length() != 0 && (l.charAt(l.length() - 1) == '(' || l.charAt(l.length() - 1) == ')')){
            if (s.charAt(i) == '('){
                a--;
            }
            if (s.charAt(i) == ')'){
                b--;
            }
            solve(s, i + 1, l.substring(0, l.length() - 1), a, b);
        }
    }

    @Test
    public void test() {
        System.out.println(removeInvalidParentheses(")d))"));
    }
}
